package com.leetcode.algorithm.y22.m06;

/**
 * 279. 完全平方数
 * 
 * https://leetcode.cn/problems/perfect-squares/
 * 
 * @author jie.deng
 *
 */
public class Question0279Solution01 {

	public int numSquares(int n) {
		int sqrt = (int) Math.sqrt(n);
		int[] sqrtArr = new int[sqrt + 1];
		for (int i = 0; i <= sqrt; i++) {
			sqrtArr[i] = i * i;
		}

		// DP状态定义
		int[] dp = new int[n + 1];

		// DP状态初始化
		dp[0] = 0;

		for (int i = 1; i <= n; i++) {
			// 最坏的情况就是每次+1
			dp[i] = i;
			for (int j = 1; j <= sqrt && i - sqrtArr[j] >= 0; j++) {
				// DP状态转移方程
				if (dp[i - sqrtArr[j]] + 1 < dp[i]) {
					dp[i] = dp[i - sqrtArr[j]] + 1;
				}
			}
		}
		return dp[n];
	}
    
}
